package cn.lbd.datastructure;

class TestDemo {
    public static void main(String[] args) {
        HeroTreeNode root = new HeroTreeNode(1, "宋江");
        HeroTreeNode heroTreeNode2 = new HeroTreeNode(2, "卢俊义");
        HeroTreeNode heroTreeNode3 = new HeroTreeNode(3, "吴用");
        HeroTreeNode heroTreeNode4 = new HeroTreeNode(4, "公孙胜");
        HeroTreeNode heroTreeNode5 = new HeroTreeNode(5, "关胜");
        HeroTreeNode heroTreeNode6 = new HeroTreeNode(6,"林冲");
        HeroTreeNode heroTreeNode7 = new HeroTreeNode(7,"秦明");
        HeroTreeNode heroTreeNode8 = new HeroTreeNode(8,"呼延灼");
        HeroTreeNode heroTreeNode9 = new HeroTreeNode(9,"呼延灼");

        BinTree binTree = new BinTree();
        root.setLeft(heroTreeNode2);
        root.setRight(heroTreeNode4);
        heroTreeNode2.setRight(heroTreeNode3);
        heroTreeNode4.setLeft(heroTreeNode5);
        heroTreeNode4.setRight(heroTreeNode6);
        heroTreeNode5.setRight(heroTreeNode7);
        heroTreeNode6.setLeft(heroTreeNode8);
        heroTreeNode6.setRight(heroTreeNode9);
        binTree.setRoot(root);

        /*binTree.preOrder();
        System.out.println();
        binTree.infixOrder();
        System.out.println();
        binTree.postOrder();*/

        /*System.out.println(binTree.preOrderSearch(2));
        System.out.println(binTree.infixOrderSearch(4));
        System.out.println(binTree.postOrderSearch(5));*/

        binTree.preOrder();
        System.out.println();
        binTree.delNode(6);
        binTree.preOrder();
        System.out.println();
        binTree.delNode(5);
        binTree.preOrder();
        /*binTree.delNode(1);
        binTree.preOrder();*/

    }
}


class BinTree {
    private HeroTreeNode root;

    public void setRoot(HeroTreeNode root) {
        this.root = root;
    }

    //前序
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

    //中序
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

    //后序
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

    //前序查找
    public HeroTreeNode preOrderSearch(int no) {
        if (this.root != null) {
            return this.root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    //中序查找
    public HeroTreeNode infixOrderSearch(int no) {
        if (this.root != null) {
            return this.root.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    //后序查找
    public HeroTreeNode postOrderSearch(int no) {
        if (this.root != null) {
            return this.root.postOrderSearch(no);
        } else {
            return null;
        }
    }


    public void delNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
            } else {
                root.delNode(no);
            }
        } else {
            System.out.println("空树，无法删除");
        }
    }


}

class HeroTreeNode {
    private int no;
    private String name;
    private HeroTreeNode left;
    private HeroTreeNode right;

    public HeroTreeNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroTreeNode getLeft() {
        return left;
    }

    public void setLeft(HeroTreeNode left) {
        this.left = left;
    }

    public HeroTreeNode getRight() {
        return right;
    }

    public void setRight(HeroTreeNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroTreeNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //后序
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }


    //前序查找
    public HeroTreeNode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        HeroTreeNode heroTreeNode = null;
        if (this.left != null) {
            heroTreeNode = this.left.preOrderSearch(no);
        }
        if (heroTreeNode != null) {
            return heroTreeNode;
        }
        if (this.right != null) {
            heroTreeNode = this.right.preOrderSearch(no);
        }
        return heroTreeNode;

    }

    //中序查找
    public HeroTreeNode infixOrderSearch(int no) {
        HeroTreeNode heroTreeNode = null;
        if (this.left != null) {
            heroTreeNode = this.left.infixOrderSearch(no);
        }
        if (heroTreeNode != null) {
            return heroTreeNode;
        }
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            heroTreeNode = this.right.infixOrderSearch(no);
        }
        return heroTreeNode;

    }


    //后序查找
    public HeroTreeNode postOrderSearch(int no) {
        HeroTreeNode heroTreeNode = null;
        if (this.left != null) {
            heroTreeNode = this.left.postOrderSearch(no);
        }
        if (heroTreeNode != null) {
            return heroTreeNode;
        }
        if (this.right != null) {
            heroTreeNode = this.right.postOrderSearch(no);
        }
        if (this.no == no) {
            return this;
        }
        return heroTreeNode;
    }


    //删除节点   (如果删除的节点有左右子树，那就根据二叉树的特性，重排子树节点位置)
    public void delNode(int no) {
        if (this.left != null && this.left.no == no) {
            if (this.left.left != null && this.left.right != null){
                this.left.left.right = this.left.right;
                this.left = this.left.left;
                return;
            }else if (this.left.left == null){
                this.left = this.left.right;
                return;
            }else if (this.left.right == null){
                this.left = this.left.left;
                return;
            }
        }
        if (this.right != null && this.right.no == no) {
            if (this.right.left != null && this.right.right != null){
                this.right.left.right = this.right.right;
                this.right = this.right.left;
                return;
            }else if (this.right.left == null){
                this.right = this.right.right;
                return;
            }else if (this.right.right == null){
                this.right = this.right.left;
                return;
            }
        }

        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }


}
